package fun.coding.leetcode;

public class ConstructBinaryTreeFromPreorderAndInorderTraversal {

	public static void main(String[] args) {
		/*
		 *             1
		 *          2     3
		 *        4  5      6
		 *          
		 *   in:   4 2 5 1 3 6
		 *   pre:  1 2 4 5 3 6    
		 * 
		 */
	}
	
	private int index = 0;
	
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0) return null;
		
		if (preorder.length != inorder.length) return null;
		return buildHelper(preorder, inorder, 0, preorder.length - 1);
	}
	
	public TreeNode buildHelper(int[] preorder, int[] inorder, int start, int end) {
		if (start > end) return null;
		
		int rootIndex = -1;
		for (int i = start; i <= end; i++) {
			if (inorder[i] == preorder[this.index]) {
				rootIndex = i;
			}
		}
		
		TreeNode root = new TreeNode(inorder[rootIndex]);
		this.index++;
		
		root.left = buildHelper(preorder, inorder, start, rootIndex - 1);
		root.right = buildHelper(preorder, inorder, rootIndex + 1, end);
		
		return root;
		
	}
}
